﻿/*
题目：直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

https://leetcode.cn/problems/max-points-on-a-line/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 哈希：枚举两个点，判断其他点是否在当前这条直线上
    //      假设 a,b,c，那么只需判断 ab 和 bc 的斜率是否相等
    // slope(ab) = (ya - yb) / (xa - xb) 
    int maxPoints(vector<vector<int>>& points) {
        int res = 1;
        int n = points.size();

        // 先确定一条直线
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = 2;

                for (int k = j + 1; k < n; k++) {
                    if (slope_eq(points[i], points[j], points[k])) {
                        sum++;
                    }
                }
                res = max(res, sum);
            }
        }

        return res;
    }

    // (y1 - y2)/(x1 - x2) == (y1 - y3)/(x1 - x3)
    bool slope_eq(vector<int>& p1, vector<int>& p2, vector<int>& p3) {
        int l = (p1[1] - p2[1]) * (p1[0] - p3[0]);
        int r = (p1[1] - p3[1]) * (p1[0] - p2[0]);
        return l == r;
    }
};